1. Field of the Invention
The present invention relates to cost minimization and more particularly to performing route optimization of services provided by multiple service providers for combined links.
2. Background Information
A computer network is a geographically distributed collection of interconnected communication links and segments for transporting data between nodes, such as computers. Many types of network segments are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect personal computers and workstations over dedicated, private communications links located in the same general physical location, such as a building or a campus. WANs, on the other hand, typically connect large numbers of geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by an intermediate network node, such as a router, having a plurality of ports that may be coupled to the networks. To interconnect geographically dispersed computer networks and/or provide Internet connectivity, many organizations rely on the infrastructure and facilities of one or more Service Providers (SPs), such as an Internet service provider (ISP). ISPs typically own one or more backbone networks that are configured to provide high-speed connections to e.g., the Internet.
To enhance availability, some organizations (clients) subscribe to one or more ISPs. Here, a router may be employed as a “gateway” that couples the client's network to the ISPs' networks. If a particular ISP's network becomes unavailable, the router may be configured to automatically shift traffic (data) away from the unavailable ISP network to an available ISP network. The router may also be configured to utilize the multiple ISP networks in a manner that enhances overall network performance. For example, if a particular ISP connection becomes heavily used thereby potentially causing poor performance, a portion of the client's traffic may be redirected by the router from the heavily used connection to another less used ISP's connection in order to improve the overall network performance of the client's network. Moreover, the router may employ a “load-sharing” scheme where traffic handled by the router is distributed among the various ISP connections in a manner that avoids overloading any one ISP connection.
A client may enter into a service level agreement (SLA) with an ISP in order to establish a level of service provided by the ISP and a price the client pays for that service. Often different ISPs employ different pricing schemes for their services. For example, some ISPs charge clients on a flat-rate basis where each client pays a fixed fee per billing period regardless of how much of the ISP's service the client uses. Other ISPs may charge clients using a tiered pricing scheme that is dependent upon the amount of the service utilized by the client. In a typical tiered pricing arrangement, an ISP may i) take periodic measurements of egress and ingress traffic carried on the client's connection to the ISP's network and aggregate the measurements to generate a “rollup value” for a rollup period, ii) generate one or more rollup values per billing period, iii) rank the rollup values for the billing period in a stack from the largest value to the smallest, iv) discard a percentage of the highest rollup values from the stack to accommodate bursting, v) apply the highest remaining rollup value in the stack to a tiered structure to determine a tier associated with the rollup value, and v) charge the client based on a cost associated with the determined tier. A rollup value, as used herein, is an aggregate of measurements taken, e.g., of ingress and/or egress traffic, over a period of time, which is referred to herein as a rollup period.
Usually in a tiered pricing scheme, the egress and ingress traffic are measured separately and the measurements are then rolled up (aggregated) either separately or in a combined manner to the produce one or more rollup values. For example, rolling up measurements separately may involve combining (aggregating) the egress measurements to generate an egress rollup value and combining (aggregating) the ingress measurements to generate an ingress rollup value. In a combined arrangement, the egress and ingress measurements may be combined (aggregated) to generate a single combined rollup value.
The method employed to determine which rollup values are discarded often varies among ISPs. Methods typically employed include sum, separate, and combined discard calculation methods. The way the rollup numbers are generated and the number of ranked stacks used often depend on the discard method. For example, the sum discard method combines egress and ingress measurements to generate the rollup values, which are then ordered on a single ranked stack. The combined and separate discard calculation methods generate separate egress and ingress rollup values that are then ordered on single and separate ranked stacks, respectively.
FIG. 1 illustrates these discard calculation methods for a rollup value discard percentage of 6% (rounded), a rollup period of one day, and a billing period of thirty days. Ranked stacks 110 and 120 illustrate the separate discard calculation method. Here, egress and ingress measurements for a rollup period are aggregated separately to produce separate egress and ingress rollup values. The rollup values for a billing period are then used to generate an egress data ranked stack 110 and an ingress data ranked stack 120. The percent of rollup values discarded is applied to each ranked stack to determine the rollup values that are discarded. In this example, thirty egress and thirty ingress rollup values are generated in the billing period and placed on the egress 110 and ingress 120 ranked stacks, respectively. The values in each stack are ordered from the largest value at the top of the stack to the smallest value at the bottom. The two largest rollup values i.e., the values for days 12 and 22 for the egress stack 110 and days 15 and 18 for the ingress stack 120, are discarded (removed) from the top of each stack. The remaining highest rollup value in each stack, i.e., the rollup value for day 3 for the egress stack 110 and day 5 for the ingress stack 120, is then used to determine the amount the client is billed for the billing period.
Stack 130 illustrates the sum discard calculation method. According to this method, each egress and ingress measurement for a rollup period are summed to produce a single rollup value per rollup period. The rollup values for a billing period are then ranked on a single stack, the percentage of rollup values discarded is applied to the stack to determine the rollup values that are discarded, the rollup values are discarded, and the client is billed based on the remaining highest rollup value, as described above. Thus, for example, for stack 130, thirty summed rollup values are generated per billing period, the top two rollup values are discarded (i.e., the rollup values for days 12 and 15), and the client is billed based on the remaining highest rollup value in the stack (i.e., the rollup value for day 22).
Stack 140 illustrates the combined discard calculation method. Here, the egress and ingress measurements are rolled up into separate rollup values. The egress and ingress rollup values for a billing period are then ranked on a single ranked stack, the percent of discarded rollup values is applied to the stack to determine the number of discarded rollup values, the discarded rollup values are discarded from the stack and the client is billed based on the remaining highest rollup value, as described above. Thus, for example, stack 140 contains sixty rollup values (i.e., thirty egress rollup values and thirty ingress rollup values), the top four rollup values are discarded (i.e., the egress rollup values for days 12 and 3, and the ingress rollup values for days 15 and 12), and the client is billed based on the remaining highest rollup value in the stack (i.e., the egress rollup value for day 7).
A client that subscribes to multiple SPs may want to maximize usage of the SPs' services while minimizing the cost associated with those services. In a data network arrangement, such as described above, this may involve continually i) monitoring access to the various SP networks, ii) determining which SP connection best suits utilization of the SPs services based on cost and iii) reconfiguring the network to distribute utilization of the services in a manner that utilizes the least-costly SP connections. Depending on the network configuration, performing these actions may be costly and arduous to implement and consequently may not be sufficiently efficient and/or accurate to effect significant cost savings.
Moreover, the billing period for different SPs may not be synchronized. For example, the billing period for a first SP may be from the beginning of the month to the end of the month whereas the billing for a second SP may start at the middle of a month and end in the middle of the next month. This may act to further complicate trying to maximize usage while minimizing cost among a plurality of SPs.
Often, users organize communication links as a group for a variety of reasons known to those skilled in the art. For example, link groups may be used for increasing the available bandwidth between two points in the network, e.g., by combining multiple smaller/slower links into a single group of links that produces a greater bandwidth value than the smaller/slower links individually. Various forms of grouped links include link bonding/aggregation, EtherChannel, multilink point-to-point protocol (PPP), which is described in RFC 1717, entitled The PPP Multilink Protocol (MP), published November 1994, etc. Other examples of link groups that will be understood by those skilled in the art include multiple VPN tunnels that are created between an enterprise network and a remote office, multiple links that share a common cost structure (e.g., as in an SLA), multiple links that are used in a common load-balancing scheme, etc.
Currently, however, routing policies and route optimization techniques (e.g., Optimized Edge Routing, OER) operate on individual links and not groups of links. As a result, conventional single-link techniques are often cumbersome when applied to groups of links, and limited control is available to users desiring greater ability to manage and optimize groups of links for a variety of purposes, in addition to those mentioned above. Particularly, users with SLAs having common cost structures for combined links do not have the ability to optimize routes based on the combined link costs. There remains a need, therefore, for a technique that performs route optimization of services provided by one or more service providers for combined links in a computer network.